package offer.day13;

public class No19match {
    /**
     * 面试题19：正则表达式匹配
     * 题目：请实现一个函数用来匹配包含‘.’和‘*’的正则表达式。
     * 模式中的字符‘.’表示任意一个字符，而‘*’表示它前面的字符可以出现任意次（包含0次）
     * 在本题中，匹配是指字符串的所有字符匹配整个模式
     * 例如：字符串“aaa”与模式“a.a”和“ab*ac*a”匹配(在ab*ac*a中表示b出现任意次,c出现任意次)，但与“aa.a”和“ab*a”均不匹配
     *
     *
     * 模式中的字符可以为:普通字符 \'.'\'*'三种情况
     * 思路:使用递归的思想,首先判断字符串和模式是否到达了末尾,到达了,则表示匹配成功.
     * 	       若字符串未到达末尾,但模式到达了末尾,则匹配失败
     * 	       若模式第二个字符是'*',字符串为达到末尾,并且模式中的第一个字符与字符串中第一个字符相匹配(或是普通字符相等,或是'.'),
     * 		则字符串和模式有三种移动情况
     * 		1>字符串移动一个,模式移动两个,都进入下一状态(执行1次x*操作)
     *      2>字符串移动一个,模式不移动(可以执行任意次)
     *      3>字符串不移动,模式移动两个(相当于执行0次x*操作)
     * 	       若模式第二个字符不是'*',那么就是'.'或者普通字符
     * 		若是'.'或者与普通字符相匹配,则该字符匹配,字符串和模式都后移一位
     *
     * 	   否则返回false
     */

    public static void main(String[] args) {

        char[] str = {'a','a'};
        char[] pattern = {'.','b','*','a'};

        System.out.println(match(str,pattern));

    }

    private static boolean match(char[] str,char[] pattern){
        if(str==null || pattern==null) return false;
        if(str.length==1){
            if(pattern.length==1){
                if(str[0]==pattern[0] || pattern[0]=='.'){
                    return true;
                }
                else{
                    return false;
                }
            }
        }
        int sindex=0;
        int pindex=0;

        return matchCore(str,sindex,pattern,pindex);
    }

    private static boolean matchCore(char[] str, int sindex, char[] pattern, int pindex) {
        if(sindex==str.length && pindex==pattern.length){
            return true;
        }
        if(sindex!=str.length && pindex==pattern.length){
            return false;
        }
        if((str[sindex]==pattern[pindex] && sindex<str.length) ||(pattern[pindex]=='.' && sindex<str.length)){
            return matchCore(str,sindex+1,pattern,pindex+1);
        }
        if(pindex+1<pattern.length && pattern[pindex+1]=='*'){
            if( (sindex<str.length && str[sindex]==pattern[pindex]) || (sindex<str.length && pattern[pindex]=='.')){
                return matchCore(str,sindex+1,pattern,pindex+2) || matchCore(str,sindex+1,pattern,pindex) || matchCore(str,sindex,pattern,pindex+2);
            }else{
                return matchCore(str,sindex,pattern,pindex+2);
            }
        }
        return false;
    }
}
